package lc;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;

public class Candy {
//    public int candy(int[] ratings) {
//    	if (ratings.length == 0) {
//    		return 0;
//    	}
//    	
//    	LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
//    	for (int i=0; i<ratings.length; i++) {
//    		map.put(i, ratings[i]);
//    	}
//    	
//    	LinkedList<Map.Entry<Integer, Integer>> list = new LinkedList<>(map.entrySet());
//    	Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
//
//			@Override
//			public int compare(Entry<Integer, Integer> o1,
//					Entry<Integer, Integer> o2) {
//				return o1.getValue() - o2.getValue();
//			}
//		});
//    	
//    	int [] num = new int [ratings.length];
//    	int minRating = list.get(0).getValue();
//    	int curr = 1;
//    	for (Map.Entry<Integer, Integer> entry : list) {
//			int key = entry.getKey();
//    		int value = entry.getValue();
//			if (value == minRating) {
//    			num[key] = curr;
//    		}
//    		else {
//    			int left = key>0 ? num[key-1] : 1;
//    			int right = key<ratings.length-1 ? num[key+1] : 1;
//    			num[key] = Math.max(left, right)+1;
//    			minRating = value;
//    			curr = num[key];
//    		}
//    	}
//    	
//    	int sum=0;
//    	for (int n : num) {
//    		sum+=n;
//    	}
//    	return sum;
//    }

	public int candy(int[] ratings) {
		// Note: The Solution object is instantiated only once and is reused by each test case.
		int nCandyCnt = 0;///Total candies
		int nSeqLen = 0;  /// Continuous ratings descending sequence length
		int nPreCanCnt = 1; /// Previous child's candy count
		int nMaxCntInSeq = nPreCanCnt;
		if(ratings.length > 0) {
			nCandyCnt++;//Counting the first child's candy.
			for(int i=1; i<ratings.length; i++)
			{
				// if r[k]>r[k+1]>r[k+2]...>r[k+n],r[k+n]<=r[k+n+1],
				// r[i] needs n-(i-k)+(Pre's) candies(k<i<k+n)
				// But if possible, we can allocate one candy to the child,
				// and with the sequence extends, add the child's candy by one
				// until the child's candy reaches that of the prev's.
				// Then increase the pre's candy as well.

				// if r[k] < r[k+1], r[k+1] needs one more candy than r[k]
				// 
				if(ratings[i] < ratings[i-1])
				{
					//Now we are in a sequence
					nSeqLen++;
					if(nMaxCntInSeq == nSeqLen)
					{
						//The first child in the sequence has the same candy as the prev
						//The prev should be included in the sequence.
						nSeqLen++;
					}
					nCandyCnt+= nSeqLen;
					nPreCanCnt = 1;
				}
				else
				{
					if(ratings[i] > ratings[i-1])
					{ 
						nPreCanCnt++;
					}
					else
					{
						nPreCanCnt = 1;
					}
					nCandyCnt += nPreCanCnt;
					nSeqLen = 0;
					nMaxCntInSeq = nPreCanCnt;
				}   
			}			
		}
		return nCandyCnt;
	}

    public static void main(String ...strings) {
    	Candy sol = new Candy();
    	int candy = sol.candy(new int [] {1, 9, 2, 1, 8, 9, 1});
    	System.out.println(candy);
    }
}
